package solution.search;

import java.util.LinkedList;
import java.util.PriorityQueue;

import org.apache.commons.lang.StringUtils;
import org.junit.Assert;
import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class MaximumInSlideWindow {

	/**
	 * Find the maximum value in a slide window of size w.
	 * 
	 * check http://www.sureinterview.com/shwqst/897001
	 * 
	 * @param A
	 *            the array from which the slide window is extracted.
	 * @param w
	 *            the size of the slide window
	 * @return result[i] is the maximum value from A[i .. i+w-1]
	 */
	public Integer[] getMaxInSlideWindow(Integer[] A, Integer w) {
		// invalid input
		if (A == null || w <= 0 || A.length - w + 1 <= 0)
			return null;

		Integer[] B = new Integer[A.length - w + 1];

		// auxiliary queue that is sorted in descending order
		LinkedList<Integer> q = new LinkedList<Integer>();

		for (int i = 0; i < A.length; i++) {
			// enqueue. Remove those smaller values
			int data = A[i];
			while (!q.isEmpty() && q.getLast() < data) {
				q.removeLast();
			}
			q.add(data);

			if (i < w - 1) {
				continue;
			}

			// dequeue. If the current number is the maximum. Also remove it
			// from the queue
			Integer max = q.get(0);
			B[i - w + 1] = max;
			if (A[i - w + 1] == max) {
				q.removeFirst();
			}
		}

		return B;
	}

	/**
	 * A slower version that using a priority queue (heap)
	 * 
	 * @param A
	 *            same as previous version
	 * @param w
	 * @return
	 */
	public Integer[] getMaxInSlideWindow2(Integer[] A, Integer w) {
		if (A == null || w <= 0 || A.length - w + 1 <= 0)
			return null;
		Integer[] B = new Integer[A.length - w + 1];
		PriorityQueue<Integer> prQ = new PriorityQueue<Integer>();

		for (int i = 0; i < A.length; i++) {
			int data = A[i];
			prQ.add(-data); // add to the priority queue

			if (i < w - 1) {
				continue;
			}
			Integer max = -prQ.peek();
			B[i - w + 1] = max;
			prQ.remove(-A[i - w + 1]); // remove the queue
		}

		return B;
	}

	@Test
	public void test() {
		Integer[] A = new Integer[] { 1, 6, 2, 8, 4, 8, 9, 1, 3, 5, 6, 7, 6, 3,
				2, 1 };
		for (int i = 1; i < 10; i++) {
			Assert.assertArrayEquals(//
					getMaxInSlideWindow(A, i), getMaxInSlideWindow2(A, i));
			System.out.println(StringUtils
					.join(getMaxInSlideWindow(A, i), ", "));
		}
	}
}
